#ifndef LIST_H
#define LIST_H

template< class T >
struct ListNode
{
    T mData;
    ListNode* prev;
    ListNode* next;
};

template< class T >
class List
{
    ListNode* head;
    ListNode* tail;
public:

    List():head(0),tail(0) {}

    /**
     * @brief insert
     * Insert node as head
     * @param t
     */
    void insert( T t )
    {
        ListNode* node = new ListNode;
        node->mData = t;
        if( !head )
        {
            tail = node;
        }

        ListNode* origHead = head;
        node->next = head;
        node->prev = 0;
        head = node;
    }

    void append( T t )
    {
        ListNode* node = new ListNode;
        node->mData = t;
        if( !tail )
        {
            head = node;
        }

        ListNode* origTail = tail;
        node->prev = tail;
        tail->next = node;
        tail = node;
    }

    ListNode* getHead() { return head; }
    ListNode* getTail() { return tail; }

    ListNode* search( T key )
    {
        ListNode* node = head;
        while( node && node->mData != key )
        {
            node = node->next;
        }

        return node;
    }

    void remove( ListNode* t )
    {
        if( t )
        {
            if( t->prev )
            {
                t->prev->next = t->next;
            }
            if( t->next )
            {
                t->next->prev = t->prev;
            }

            delete t;
        }
    }
};

/**
 * A list with sentinel as head/tail at the same time.
 * Sentinel list is actually a circular doubly linked list
 */

template< class T >
class SentinelList
{
    ListNode sentinel;
public:
    SentinelList()
    {
        sentinel.prev = &sentinel;
        sentinel.next = &sentinel;
    }

    void insert( T t )
    {
        ListNode* node = new ListNode;
        node->mData = t;
        node->next = sentinel.next;
        node->prev = &sentinel;
        sentinel.next = node;
    }

    void append( T t )
    {
        ListNode* node = new ListNode;
        node->mData = t;
        node->prev = sentinel.prev;
        node->next = &sentinel;
        sentinel.prev = node;
    }

    ListNode* search( T key )
    {
        ListNode* node = sentinel.next;
        /*
         * We can set node to a value that never appears for regular key
         * to omit node!=&sentinel in while() loop
         */
        while( node != &sentinel && node->mData!= key )
        {
            node = node->next;
        }

        if( node == &sentinel )
        {
            node = 0;
        }

        return node;
    }

    void remove( ListNode* t )
    {
        t->prev->next = t->next;
        t->next->prev = t->prev;
        delete t;
    }
};

template< class T >
class SingleDirectList
{
    ListNode* head;
public:
    SingleDirectList():head(0){}

    void insert( T t )
    {

    }
    void remove( )
    {

    }
    void search( T key )
    {

    }
    void reverse()
    {

    }
};

#endif // LIST_H
